"""
给定一个数组A，再给定一些操作
每次操作[s, e]，表示将A[s, e]全部减一
问最多抛弃多少次操作，可以使得剩下的操作仍然能将数组操作为非正
贪心
for 数组的每一个位置i:
   在所有满足 i in [s, e] 的操作中，优先选取e大的进行操作
   对每一个操作，将[s, e]全部减一，使用树状数组维护差分数组完成
操作首先按左端点排序，然后依次加入队列，队列按右端点排序即可
"""
import heapq
from typing import Iterable, List
from typing import Union

class FenwickTree(object):
    def __init__(self, n: int) -> None:
        self.N = n
        self.data = [0 for i in range(n + 1)]
        return
    def modify(self, pos: int, delta: int) -> None:
        k = pos
        while k <= self.N:
            self.data[k] += delta
            k += FenwickTree.lowbit(k)
        return
    def query(self, param: Union[int, Iterable]) -> int:
        if isinstance(param, Iterable):
            return self.query(param[1]) - self.query(param[0] - 1)
        assert isinstance(param, int)
        ans, k = 0, param
        while k > 0:
            ans += self.data[k]
            k -= FenwickTree.lowbit(k)
        return ans

    @staticmethod
    def lowbit(x: int) -> int:
        return x & -x

class T(object):
    def __init__(self, a: int, b: int) -> None:
        self.left = a
        self.right = b
        return
    def __lt__(self, other: 'T') -> bool:
        if self.right != other.right: return self.right > other.right
        return self.left < other.left

class Solution:
    def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:
        op = []
        for a, b in queries:
            op.append(T(a + 1, b + 1))
        # 按left关键字排序
        op.sort(key=lambda x: x.left)
        n = len(nums)
        bt = FenwickTree(n + 1)
        bt.modify(1, nums[0])
        for i in range(1, n):
            bt.modify(i + 1, nums[i] - nums[i - 1])
        
        k = 0
        Q = []
        c = 0
        for i in range(1, n + 1):
            while k < len(op):
                if op[k].left <= i: heapq.heappush(Q, op[k])
                else: break
                k += 1
            while True:
                tmp = bt.query(i)
                if tmp <= 0: break

                if len(Q) == 0: return -1
                top = heapq.heappop(Q)
                if top.left > i or top.right < i: continue

                bt.modify(i, -1)
                bt.modify(top.right + 1, 1)
                c += 1            
        return len(op) - c